package 区间;

import org.junit.Test;

import java.util.*;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;

/*
    看算法模板-区间
*/
public class 最少删除几个区间让区间不重叠435_自排序法 {

    @Test
    public void test() {
        int[][] g = {{1,100},{11,22},{1,11},{2,12}};
        System.out.println(eraseOverlapIntervals(g));
    }
    public int eraseOverlapIntervals(int[][] g) {
        Arrays.sort(g, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if(a[0]==b[0]){
                    return b[1]-a[1];
                }
                return a[0]-b[0];
            }
        });
        //1起, z形：父右和cur左比
        int faRight = g[0][1];
        int count =0;
        for (int i = 1; i < g.length; i++) {
            //这里是faRight,不是g[i-1][0] -> 为了尽量让后面少重叠
            //if(g[i][0]<g[i][1]){
            if(g[i][0] < faRight){
                count++;
                //这里也是faRight
                //faRight = Math.min(g[i-1][1],g[i][1]);
                faRight = Math.min(faRight,g[i][1]);
            }else {
                faRight = g[i][1];
                continue;
            }
        }
        return count;
    }
}
